﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HuffmanTree
{
	class Program
	{
		static void Main(string[] args)
		{
			//有四个叶节点
            int leafNum = 4;
            //赫夫曼树中的节点总数
            int huffmanNodes = 2 * leafNum - 1;
            //各节点的权值
            int[] weight = { 5, 7, 2, 13 };
            string[] alphabet = { "A", "B", "C", "D" };
            string testCode = "DBDBDABDCDADBDADBDADACDBDBD";
            //赫夫曼树用数组来保存，每个赫夫曼都作为一个实体存在
            HuffmanTree[] huffman = new HuffmanTree[huffmanNodes].Select(i => new HuffmanTree() { }).ToArray();
            HuffmanTreeManager manager = new HuffmanTreeManager();
            manager.CreateTree(huffman, leafNum, weight);
            string[] huffmanCode = manager.HuffmanCoding(huffman, leafNum);
            for (int i = 0; i < leafNum; i++)
            {
                Console.WriteLine("字符：{0}，权重:{1},编码为:{2}", alphabet[i], huffman[i].Weight, huffmanCode[i]);
            }
            Console.WriteLine("原始的字符串为：" + testCode);
            string encode = manager.Encode(huffmanCode, alphabet, testCode);
            Console.WriteLine("被编码的字符串为：" + encode);
            string decode = manager.Decode(huffman, huffmanNodes, alphabet, encode);
            Console.WriteLine("解码后的字符串为：" + decode);
			Console.ReadLine();
		}
	}

	#region 哈夫曼树结构

	public class HuffmanTree
	{
		//权值
		public int Weight { get; set; }
		//父节点
		public int Parent { get; set; }
		//左节点
		public int Left { get; set; }
		//右节点
		public int Right { get; set; }
	}

	#endregion

	#region 哈夫曼树的操作类

	public class HuffmanTreeManager
	{
		#region 哈夫曼树的创建
		
		/// <summary>
		/// 哈夫曼树的创建  (当叶子节点为N个，则需要N-1步就能搭建赫夫曼树。当叶子节点为N个，则赫夫曼树的节点总数为:(2*N)-1个)。
		/// </summary>
		/// <param name="huffman">哈夫曼树</param>
		/// <param name="leafNum">叶子节点</param>
		/// <param name="weight">节点权重</param>
		/// <returns></returns>
		public HuffmanTree[] CreateTree(HuffmanTree[] huffman,int leafNum,int[] weight)
		{
			//哈夫曼树的节点总数
			int huffmanNode = 2*leafNum - 1;

			//初始化节点，赋予叶子节点值
			for (int i = 0; i < huffmanNode; i++)
			{
				if(i < leafNum)
				{
					huffman[i].Weight = weight[i];
				}
			}

			//这里面也要注意，4个节点，其实只要3步就可以构造哈夫曼树
			for (int i = leafNum; i < huffmanNode; i++)
			{
				int minIndex1;
				int minIndex2;
				SelectNode(huffman, i, out minIndex1, out minIndex2);

				//最后得出minIndex1和minIndex2中实体的weight最小
				huffman[minIndex1].Parent = i;
				huffman[minIndex2].Parent = i;

				huffman[i].Left = minIndex1;
				huffman[i].Right = minIndex2;

				huffman[i].Weight = huffman[minIndex1].Weight + huffman[minIndex2].Weight;
			}
			return huffman;
		}

		#endregion

		#region 选出叶子节点中最小的节点

		public void SelectNode(HuffmanTree[] huffman,int searcheNodes,out int minIndex1,out int minIndex2)
		{
			HuffmanTree minNode1 = null;
			HuffmanTree minNode2 = null;
			//最小节点在哈夫曼树中的下标
			minIndex1 = minIndex2 = 0;
			//查找范围
			for (int i = 0; i < searcheNodes; i++)
			{
				//只有独根树才能进入查找范围
				if (huffman[i].Parent==0)
				{
					//如果为null，则认为当前实体为最小
					if(minNode1==null)
					{
						minIndex1 = i;
						minNode1 = huffman[i];
						continue;
					}
					//如果为null 则认为当前实体为最小
					if(minNode2==null)
					{
						minIndex2 = i;
						minNode2 = huffman[i];
						//交换一个位置，保证minIndex1为最小，为后面判断做准备
						if(minNode1.Weight > minNode2.Weight)
						{
							//交换节点
							var temp = minNode1;
							minNode1 = minNode2;
							minNode2 = temp;

							//下标交换
							var tempIndex = minIndex1;
							minIndex1 = minIndex2;
							minIndex2 = tempIndex;
							
							continue;
						}
					}

					if(minNode1!=null && minNode2!=null)
					{
						if(huffman[i].Weight <= minNode1.Weight)
						{
							//将min1临时转存给min2
							minNode2 = minNode1;
							minNode1 = huffman[i];

							//记录在数组中的下标
							minIndex2 = minIndex1;
							minIndex1 = i;
						}
						else
						{
							if(huffman[i].Weight < minNode2.Weight)
							{
								minNode2 = huffman[i];
								minIndex2 = i;
							}
						}
					}
				}
			}
		}

		#endregion

		#region 哈夫曼编码

		public string[] HuffmanCoding(HuffmanTree[] huffman,int leafNum)
		{
			int current = 0;
			int parent = 0;
			string[] huffmanCode = new string[leafNum];
			//四个叶子节点的循环
			for (int i = 0; i < leafNum; i++)
			{
				//单个字符的编码串
				string codeTemp = string.Empty;
				current = i;
				//第一次获取最左节点
				parent = huffman[current].Parent;
				while (parent!=0)
				{
					//如果父节点的左子树等于当前节点就标记为0
					if (current==huffman[parent].Left)
					{
						codeTemp += "0";
					}
					else
					{
						codeTemp += "1";
					}
					current = parent;
					parent = huffman[parent].Parent;
				}
				huffmanCode[i]=new string(codeTemp.Reverse().ToArray());
			}
			return huffmanCode;
		}

		#endregion

		#region 对指定字符进行压缩

		public string Encode(string[] huffmanCode,string[] alphabet,string test)
		{
			//返回的0，1代码
			string encodeStr = string.Empty;
			//对每个字符进行编码
			for (int i = 0; i < test.Length; i++)
			{
				//在模版里面查找
				for (int j = 0; j < alphabet.Length; j++)
				{
					if (test[i].ToString()==alphabet[j])
					{
						encodeStr += huffmanCode[j];
					}
				}
			}
			return encodeStr;
		}

		#endregion

		#region 对指二进制进行解压

		public string Decode(HuffmanTree[] huffman, int huffmanNodes, string[] alphabet,string test)
		{
			string decodeStr = string.Empty;
			//对每个字符进行编码
			for (int i = 0; i < test.Length;)
			{
				int j = 0;
				//在模版里面查找
				for (j=huffmanNodes-1; (huffman[j].Left!=0 || huffman[j].Right!=0);)
				{
					if (test[i].ToString() == "0")
					{
						j = huffman[j].Left;
					}
					if (test[i].ToString()=="1")
					{
						j = huffman[j].Right;
					}
					i++;
				}
				decodeStr += alphabet[j];
			}
			return decodeStr;
		}

		#endregion
	}

	#endregion
}
